package backtracking.combination;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 93. 复原 IP 地址
 * <p>
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * <p>
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入'.' 来形成。你 不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 */
public class N93_RestoreIpAddress {
    private List<String> res = new LinkedList<>();
    private StringBuilder sb;

    private boolean isValid(StringBuilder sb, int l, int r) {
        if (l > r) return false;
        if (sb.charAt(l) == '0' && l != r) return false;
        long num = Long.parseLong(sb.substring(l, r + 1));
        return num <= 255;
    }

    private void backtracking(StringBuilder sb, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isValid(sb, startIndex, sb.length() - 1)) {
                res.add(sb.toString());
            }
            return;
        }
        for (int i = startIndex; i < sb.length(); i++) {
            if (isValid(sb, startIndex, i)) {
                sb.insert(i + 1, '.');
                backtracking(sb, i + 2, pointNum + 1);
                sb.deleteCharAt(i + 1);
            } else break;
        }
    }

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) return res;
        sb = new StringBuilder(s);
        backtracking(sb, 0, 0);
        return res;
    }

    public static void main(String[] args) {
        N93_RestoreIpAddress solution = new N93_RestoreIpAddress();
        List<String> strings = solution.restoreIpAddresses("0279245587303");
        for (String string : strings) {
            System.out.println(string);
        }
    }
}
